package 力扣._322_零钱兑换;

import java.util.Arrays;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        //硬币无限-》完全背包，所需硬币最少——》
        //dp[j]: 装满容量为j背包最少需要dp[j]个硬币
        //dp[j] = min(dp[j - coins[i]] + 1, dp[j])
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = 99999999;
        }
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[amount] == 99999999 ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] nums = new int[2];
        int amount = 3;
        int i = new Solution().coinChange(nums, amount);
        System.out.println(i);
        System.out.println(Integer.MAX_VALUE);
    }
}
